package com.c2b.algorithm.leetcode.base;

import java.util.Stack;

/**
 * <a href='https://leetcode.cn/problems/design-an-expression-tree-with-evaluate-function/'>设计带解析函数的表达式树(Design an Expression Tree With Evaluate Function)</a>
 * <p>给定一个算术表达式的后缀表示法的标记（token） postfix ，构造并返回该表达式对应的二叉表达式树。</p>
 * <p>后缀表示法是一种将操作数写在运算符之前的表示法。例如，表达式 4*(5-(2+7)) 的后缀表示法表示为数组 postfix = ["4","5","7","2","+","-","*"] 。</p>
 * <p>抽象类 Node 需要用于实现二叉表达式树。我们将通过 evaluate 函数来测试返回的树是否能够解析树中的值。你不可以移除 Node 类，但你可以按需修改此类，也可以定义其他类来实现它。</p>
 * <p>二叉表达式树是一种表达算术表达式的二叉树。二叉表达式树中的每一个节点都有零个或两个子节点。 叶节点（有 0 个子节点的节点）表示操作数，非叶节点（有 2 个子节点的节点）表示运算符： '+' （加）、 '-' （减）、 '*' （乘）和 '/' （除）。</p>
 * <p>我们保证任何子树对应值的绝对值不超过 10^9 ，且所有操作都是有效的（即没有除以零的操作）</p>
 * <p><b>进阶： 你可以将表达式树设计得更模块化吗？例如，你的设计能够不修改现有的 evaluate 的实现就能支持更多的操作符吗？</b></p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入： s = ["3","4","+","2","*","7","/"]
 *                          /
 *                        /  \
 *                       *    7
 *                      / \
 *                     +   2
 *                    / \
 *                   3   4
 *      输出： 2
 *      解释： 此表达式可解析为上述二叉树，其对应表达式为 ((3+4)*2)/7) = 14/7 = 2.
 *
 * 示例 2:
 *      输入: s = ["4","5","7","2","+","-","*"]
 *                          *
 *                        /   \
 *                       4     -
 *                            / \
 *                           5   +
 *                              / \
 *                             2   7
 *      输出: -16
 *      解释: 此表达式可解析为上述二叉树，其对应表达式为 4*(5-(2+7)) = 4*(-4) = -16.
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示:</b>
 * <ul>
 *     <li>1 <= s.length < 100</li>
 *     <li>s.length 是奇数。</li>
 *     <li>s 包含数字和字符 '+' 、 '-' 、 '*' 以及 '/' 。</li>
 *     <li>如果 s[i] 是数，则对应的整数不超过 105 。</li>
 *     <li>s 保证是一个有效的表达式。</li>
 *     <li>结果值和所有过程值的绝对值均不超过 10^9 。</li>
 *     <li>保证表达式不包含除以零的操作。</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/4 16:30
 */
public class LC1628DesignExpressionTreeWithEvaluateFunction_M {

    abstract static class Node {

        public abstract int evaluate();

        public static Node from(String value) {
            switch (value) {
                case "+":
                    return new AdditionNode();
                case "-":
                    return new SubtractionNode();
                case "*":
                    return new MultiplicationNode();
                case "/":
                    return new DivisionNode();
                default:
                    return new NumericalNode(value);
            }
        }
    }

    abstract static class OperatorNode extends Node {
        protected Node left;
        protected Node right;

        public void setLeft(Node left) {
            this.left = left;
        }

        public void setRight(Node right) {
            this.right = right;
        }
    }

    static class AdditionNode extends OperatorNode {
        @Override
        public int evaluate() {
            return left.evaluate() + right.evaluate();
        }
    }

    static class SubtractionNode extends OperatorNode {
        @Override
        public int evaluate() {
            return left.evaluate() - right.evaluate();
        }
    }

    static class MultiplicationNode extends OperatorNode {
        @Override
        public int evaluate() {
            return left.evaluate() * right.evaluate();
        }
    }

    static class DivisionNode extends OperatorNode {
        @Override
        public int evaluate() {
            return left.evaluate() / right.evaluate();
        }
    }

    static class NumericalNode extends OperatorNode {
        private final String value;

        public NumericalNode(String value) {
            this.value = value;
        }

        @Override
        public int evaluate() {
            return Integer.parseInt(value);
        }
    }

    static class TreeBuilder{
        Node buildTree(String[] postfix) {
            Stack<Node> stack = new Stack<>();
            for (String s : postfix) {
                Node node = Node.from(s);
                if (node instanceof NumericalNode) {
                    // 如果是数字，直接入栈
                    stack.push(node);
                } else if (node instanceof OperatorNode) {
                    // 如果是操作符，从栈中弹出两个元素，计算后入栈
                    OperatorNode operatorNode = (OperatorNode) node;
                    operatorNode.setRight(stack.pop());
                    operatorNode.setLeft(stack.pop());
                    stack.push(operatorNode);
                } else {
                    throw new IllegalArgumentException("node should be instance of NumericalNode or OperatorNode");
                }
            }
            return stack.pop();
        }
    }

}
